class Solution
{
public:
    bool isPossible(int n, vector<vector<int>> &edges)
    {
        unordered_map<int, unordered_set<int>> adjTable;
        for (auto &edge : edges)
        {
            adjTable[edge[0]].insert(edge[1]);
            adjTable[edge[1]].insert(edge[0]);
        }
        vector<int> oddDegreeNodes;

        for (auto &[node, nearNodes] : adjTable)
        {
            if (nearNodes.size() & 1)
            {
                oddDegreeNodes.push_back(node);
            }
        }
        auto check = [&](int i, int j) -> bool
        {
            return !adjTable[oddDegreeNodes[i]].count(oddDegreeNodes[j]);
        };

        // 最多添加两条边，于是度为奇数的点的个数只能是0，2，4
        // 0个度为奇数的点
        if (oddDegreeNodes.size() == 0)
        {
            return true;
        }
        // 2个度为奇数的点，用一条边将它们相连，或者用两条边连接到同一个其他点上
        if (oddDegreeNodes.size() == 2)
        {
            if (check(0, 1))
            {
                return true;
            }
            for (int i = 1; i <= n; ++i)
            {
                if (i == oddDegreeNodes[0] || i == oddDegreeNodes[1])
                {
                    continue;
                }
                if (!adjTable[i].count(oddDegreeNodes[0]) && !adjTable[i].count(oddDegreeNodes[1]))
                {
                    return true;
                }
            }
        }
        // 4个度为奇数的点，只能是两组相连
        if (oddDegreeNodes.size() == 4)
        {
            if (check(0, 1) && check(2, 3))
            {
                return true;
            }
            if (check(0, 2) && check(1, 3))
            {
                return true;
            }
            if (check(0, 3) && check(1, 2))
            {
                return true;
            }
            return false;
        }
        return false;
    }
};